package gold.gold05;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 好题目, 猛男落泪。
 * 类似于一个叠箱子的题, 箱子由大到小放置, 而且箱子是3维的。
 * 先按照身高排序, 然后会是这个排序结果第二维的一个最长递增子串。注意这个相等问题。
 * 这里身高/体重有一个相等的不能堆, 所以在判断的时候还需要对已排序的身高部分进行判断。
 *
 * 有两种dp方法, 一种O(n2), 以每个节点为结尾的子串需要和前面每一个节点的最大情况相比较。
 * 一种O(nlogn), 创建一个等效长度的辅助序列。
 */
public class S1708马戏团人塔 {
    /**
     * 18, 写一下对这个辅助串的理解。
     * 遇到最大的往后插入, 表示长度+1比较好理解。
     * 比如排序4 2 3 1 5, 首先dp: 4, 然后2来了, 替换4得到dp: 2; 3插入, dp: 2 3;
     * 1替换2, dp: 1 3; 5插入, dp: 1 3 5; 最长子序列长度与dp相同为3, 但是其实是2 3 5, 与dp不相同。
     * 理解是这里1替换2, 实际上是指在dp中找到一个位置, 这个位置所在的长度, 为以1结尾的递增子串的最大长度。
     * 每一次替换, 实际上都是在记录每一个数字结尾的最大长度。因为增长只看最后一个点。
     */
    public int bestSeqAtIndex3(int[] height, int[] weight) {
        int len = height.length;
        if(len == 0) return 0;
        int[][] allInfo = new int[len][2];
        for(int i = 0; i < len; i++){
            allInfo[i][0] = height[i];
            allInfo[i][1] = weight[i];
        }
        // 注意这里排序和O(n2)的dp不一样。一定是先按第一维递增再按第二维递减, 这样在找第二维的递增子串的时候就不用考虑第一维是否相等的问题了
        // 因为第一维相等的话, 这几个相等身高对应的体重一定没办法严格递增。
        Arrays.sort(allInfo, (a, b)->{return a[0] - b[0] == 0? b[1] - a[1]: a[0] - b[0];});
        int[] record = new int[len]; // 单纯寻找这个record的最长严格递增子串。
        for(int i = 0; i < len; i++) record[i] = allInfo[i][1];
        // 下面那个方法, 用数组+一个位置来, 更快。不必看到变长就用集合类。
        List<Integer> sortList = new ArrayList<>();
        sortList.add(record[0]);
        //loop1:
        for(int i: record){
            if(i > sortList.get(sortList.size() - 1)){
                sortList.add(i);
            }
            else{
                int high = sortList.size() - 1;
                int low = 0;
                int mid;
                while(high > low){
                    mid = (high + low) >> 1;
                    if(sortList.get(mid) > i){
                        high = mid;
                    }else if(sortList.get(mid) < i){
                        low = mid + 1;
                    }else{
                        // 这里这个=改了很久很久, 难以发现的问题, 这里的查找位置有点错, =的情况下返回的是比他大的值。。
                        low = mid;
                        break;
                        //continue loop1;
                    }
                }
                sortList.set(low, i);
            }
        }

        return sortList.size();
    }
    /**
     * 别人的方法。注意这个binarySearch的使用, 非常好。
     */
    public int bestSeqAtIndex2(int[] height, int[] weight) {
        int len = height.length;
        if(len == 0) return 0;
        int[][] allInfo = new int[len][2];
        for(int i = 0; i < len; i++){
            allInfo[i][0] = height[i];
            allInfo[i][1] = weight[i];
        }
        // 注意这里排序和O(n2)的dp不一样。
        Arrays.sort(allInfo, (a, b)-> a[0] - b[0] == 0? b[1] - a[1]: a[0] - b[0]);
        int[] dp = new int[len];
        int res = 0;
        for (int[] pair : allInfo) {
            // 这里巧妙地用了binarySearch查找不到的时候的返回结果。
            int i = Arrays.binarySearch(dp, 0, res, pair[1]);
            if (i < 0)
                i = -(i + 1);
            dp[i] = pair[1];
            if (i == res)
                ++res;
        }
        return res;
    }

    /**
     * 直白的动态规划, 超时。
     */
    public int bestSeqAtIndex(int[] height, int[] weight) {
        int len = height.length;
        if(len == 0) return 0;
        int[][] allInfo = new int[len][2];
        for(int i = 0; i < len; i++){
            allInfo[i][0] = height[i];
            allInfo[i][1] = weight[i];
        }
        // 排序所占时间非常小, 看来nlogn复杂度在测试用例超长情况下还是比n2好太多。
        Arrays.sort(allInfo, (a, b)->{return a[0] - b[0] == 0? a[1] - b[1]: a[0] - b[0];});
        // System.out.println(Arrays.deepToString(allInfo));

         int[] record = new int[len]; // 记录以每个位置结尾的最长递增子串
         record[0] = 1;
         // 二维数组索引是有计算的, 换成1维可以节约一点时间(多通过4个用例, 还是超时了)。
         for(int i = 0; i < len; i++){
             height[i] = allInfo[i][0];
             weight[i] = allInfo[i][1];
         }
         for(int i = 1; i < len; i++){
             int tempRecord = 1;
             for(int j = 0; j < i; j++){
                 if(weight[i] > weight[j] & height[i] > height[j]){
                     tempRecord = Math.max(tempRecord, record[j] + 1);
                 }
             }
             record[i] = tempRecord;
         }
        // 被替换的部分。
        // for(int i = 1; i < len; i++){
        //     int tempRecord = 1;
        //     for(int j = 0; j < i; j++){
        //         if(allInfo[i][1] > allInfo[j][1] & allInfo[i][0] > allInfo[j][0]){
        //             tempRecord = Math.max(tempRecord, record[j] + 1);
        //         }
        //     }
        //     record[i] = tempRecord;
        // }
        int res = 0;
        for(int i: record) res = Math.max(res, i);
        return res;
    }
}
